Namespacing everything to /UVa.
[andmenj-acm.git] / UVa / 11515 - Cranes / a.cpp
blob4c3354fe23e8ce9897cd876752919a482531e13e
1 /*
2 Problem: A - Cranes
3 Author: Andrés Mejía-Posada
4 (http://blogaritmo.factorcomun.org)
6 */
8 using namespace std;
9 #include <algorithm>
10 #include <iostream>
11 #include <iterator>
12 #include <sstream>
13 #include <fstream>
14 #include <cassert>
15 #include <climits>
16 #include <cstdlib>
17 #include <cstring>
18 #include <string>
19 #include <cstdio>
20 #include <vector>
21 #include <cmath>
22 #include <queue>
23 #include <deque>
24 #include <stack>
25 #include <map>
26 #include <set>
28 #define D(x) cout << #x " is " << x << endl
30 double pi = acos(-1.0);
32 struct crane{
33 int x, y, r;
36 inline double distsqr(int x1, int y1, int x2, int y2){ return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);}
38 bool colapse(crane &a, crane &b){
39 return (distsqr(a.x,a.y, b.x,b.y) <= (a.r + b.r)*(a.r + b.r) );
42 int main(){
43 int C;
44 for(cin >> C; C--;){
45 int n;
46 cin >> n;
48 vector<crane> v(n);
49 for (int i=0; i<n; ++i) cin >> v[i].x >> v[i].y >> v[i].r;
51 vector<pair<int, int> > bad;
52 for (int i=0; i<n; ++i)
53 for (int j=i+1; j<n; ++j)
54 if (colapse(v[i], v[j])){
55 bad.push_back(make_pair(i, j));
56 //cout << "choque " << i << " " << j << endl;
59 int ans = 0;
61 for (int mask=1; mask < (1<<n); ++mask){
62 bool ok = true;
63 for (int i=0; i<bad.size(); ++i){
64 int &x = bad[i].first, &y = bad[i].second;
65 if ( (mask & (1 << x)) && (mask & (1 << y)) ){
66 ok = false;
67 break;
71 if (!ok) continue;
73 int sum = 0;
74 for (int i=0; i<n; ++i){
75 if (mask & (1 << i)){
76 sum += v[i].r*v[i].r;
79 ans = max(ans, sum);
81 cout << ans << endl;
85 return 0;